#include "string_array.h"
#include <cstring>

using namespace std;
myStr::myStr(const char*s){
    if (s == nullptr) {
        length = 0;
        data = new char[1];
        data[0] = '\0';
    } else {
        length = std::strlen(s);
        data = new char[length + 1];
        std::strcpy(data, s);
    }
    next = nullptr;
    nextVal = nullptr;
}

myStr::~myStr(){

    if (data != nullptr) {
        delete[] data;
    }
    if (next != nullptr) {
        delete[] next;
    }
    if (nextVal != nullptr) {
        delete[] nextVal;
    }
    data = nullptr;
    next = nullptr;
    nextVal=nullptr;
}

int simpleMatch(const myStr& S, const myStr& T) {
    // 检查T是否为空
    if (T.length == 0) {
        return 1; // 空串匹配位置1
    }
    
    // 检查S长度是否小于T长度
    if (S.length < T.length) {
        return -1; // S比T短，不可能匹配
    }
    
    for (int i = 0; i <= S.length - T.length; i++) {
        int j = 0;
        while (j < T.length && S.data[i + j] == T.data[j]) {
            j++;
        }
        if (j == T.length) {
            return i + 1; // 返回1-based位置
        }
    }
    return -1; // 未找到匹配
}

void myStr::kmp_next()
{
    if (next != nullptr) delete[] next;
    next = new int[length]; // 分配length个空间，从0开始索引
    
    if (length == 0) return;
    
    // 使用从-1开始的索引系统计算next数组
    int* tempNext = new int[length];
    tempNext[0] = -1;
    
    int j = 0;
    int k = -1;
    
    while (j < length - 1) {
        if (k == -1 || data[j] == data[k]) {
            j++;
            k++;
            tempNext[j] = k;
        } else {
            k = tempNext[k];
        }
    }
    
    // 将标准next数组（从-1开始）转换为从0开始的数组
    for (int i = 0; i < length; i++) {
        next[i] = tempNext[i] + 1;
    }
    
    delete[] tempNext;
}
void myStr::kmp_nextVal() {
    if (next == nullptr) kmp_next();
    if (nextVal != nullptr) delete[] nextVal;
    nextVal = new int[length]; // 分配length个空间，从0开始索引
    
    if (length == 0) return;
    
    // 使用从-1开始的索引系统计算next数组
    int* tempNext = new int[length];
    tempNext[0] = -1;
    
    int j = 0;
    int k = -1;
    
    while (j < length - 1) {
        if (k == -1 || data[j] == data[k]) {
            j++;
            k++;
            tempNext[j] = k;
        } else {
            k = tempNext[k];
        }
    }
    
    // 基于tempNext计算标准的nextVal数组（从-1开始）
    int* tempNextVal = new int[length];
    tempNextVal[0] = -1;
    
    for (int i = 1; i < length; i++) {
        if (data[i] != data[tempNext[i]]) {
            tempNextVal[i] = tempNext[i];
        } else {
            tempNextVal[i] = tempNextVal[tempNext[i]];
        }
    }
    
    // 将标准nextVal数组（从-1开始）转换为从0开始的数组
    for (int i = 0; i < length; i++) {
        nextVal[i] = tempNextVal[i] + 1;
    }
    
    delete[] tempNext;
    delete[] tempNextVal;
}

int kmpMatch(const myStr& S, const myStr& T) {
    // 检查T是否为空
    if (T.length == 0) {
        return 1; // 空串匹配位置1
    }
    
    // 检查S长度是否小于T长度
    if (S.length < T.length) {
        return -1; // S比T短，不可能匹配
    }
    
    // 创建临时副本用于计算next数组
    myStr tempT = T;
    tempT.kmp_next(); // 确保next数组已计算
    
    int i = 0; // S的索引（0-based）
    int j = 0; // T的索引（0-based）
    
    while (i < S.length && j < T.length) {
        if (j == 0 || S.data[i] == T.data[j]) {
            i++;
            j++;
        } else {
            if (j > 0) {
                j = tempT.next[j - 1]; // 使用next数组回溯（注意：next数组是0-based）
            } else {
                i++;
            }
        }
    }
    
    if (j == T.length) {
        return i - j + 1; // 返回1-based位置
    } else {
        return -1; // 未找到匹配
    }
}


bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    // 参数检查：start从1开始
    if (start < 1 || start > S.length) {
        return false;
    }
    
    // 检查T是否为空
    if (T.length == 0) {
        return false;
    }
    
    // 从start-1位置开始查找T
    int pos = -1;
    int start_idx = start - 1; // 转换为0-based索引
    
    // 直接进行简单的字符串匹配
    for (int i = start_idx; i <= S.length - T.length; i++) {
        bool match = true;
        for (int j = 0; j < T.length; j++) {
            if (S.data[i + j] != T.data[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            pos = i; // 0-based的起始位置
            break;
        }
    }
    
    if (pos == -1) {
        return false; // 没找到
    }
    
    // 计算新字符串的长度
    int new_length = S.length - T.length + V.length;
    char* new_data = new char[new_length + 1]; // +1 for null terminator
    
    // 复制T之前的部分
    int copy_pos = 0;
    for (int i = 0; i < pos; i++) {
        new_data[copy_pos++] = S.data[i];
    }
    
    // 复制V
    for (int i = 0; i < V.length; i++) {
        new_data[copy_pos++] = V.data[i];
    }
    
    // 复制T之后的部分
    for (int i = pos + T.length; i < S.length; i++) {
        new_data[copy_pos++] = S.data[i];
    }
    
    new_data[copy_pos] = '\0'; // 添加字符串结束符
    
    // 重要：在更新S之前，先删除原来的next和nextVal数组，因为字符串内容已改变
    if (S.next != nullptr) {
        delete[] S.next;
        S.next = nullptr;
    }
    if (S.nextVal != nullptr) {
        delete[] S.nextVal;
        S.nextVal = nullptr;
    }
    
    // 更新S
    delete[] S.data;
    S.data = new_data;
    S.length = new_length;
    
    return true;
}

myMatrix::myMatrix() : nodeList(nullptr), rowNum(0), colNum(0), nodeNum(0) {
    // 所有成员初始化为0或nullptr
}

myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* data) {
    // 初始化基本属性
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    
    // 为非零元素分配内存
    if (nNum > 0) {
        nodeList = new matrixNode[nNum];
        
        // 从输入数据中提取三元组信息
        for (int i = 0; i < nNum; i++) {
            nodeList[i].row = data[i * 3];      // 第i个三元组的行号
            nodeList[i].col = data[i * 3 + 1];  // 第i个三元组的列号
            nodeList[i].value = data[i * 3 + 2];// 第i个三元组的值
        }
    } else {
        nodeList = nullptr;
    }
}

myMatrix::~myMatrix() {
    if (nodeList != nullptr) {
        delete[] nodeList;
        nodeList = nullptr;
    }
}

void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    // 如果当前矩阵为空，直接返回空矩阵
    if (nodeNum == 0) {
        T = myMatrix();
        return;
    }
    
    // 1. 初始化转置矩阵的基本属性
    T.rowNum = colNum;    // 转置后行数 = 原列数
    T.colNum = rowNum;    // 转置后列数 = 原行数
    T.nodeNum = nodeNum;  // 非零元素个数不变
    
    // 为转置矩阵分配内存
    T.nodeList = new matrixNode[nodeNum];
    
    // 2. 计算原矩阵每列的非零元素个数（即转置后每行的非零元素个数）
    int* colCount = new int[colNum + 1](); // 下标从1开始，初始化为0
    for (int i = 0; i < nodeNum; i++) {
        colCount[nodeList[i].col]++;
    }
    
    // 3. 计算转置后每行第一个非零元素的位置
    int* startPos = new int[colNum + 1](); // 下标从1开始
    startPos[1] = 0;
    for (int i = 2; i <= colNum; i++) {
        startPos[i] = startPos[i - 1] + colCount[i - 1];
    }
    
    // 4. 进行转置操作
    for (int i = 0; i < nodeNum; i++) {
        int col = nodeList[i].col;
        int pos = startPos[col];
        
        // 将元素转置后放入合适位置
        T.nodeList[pos].row = nodeList[i].col;    // 行 = 原列
        T.nodeList[pos].col = nodeList[i].row;    // 列 = 原行
        T.nodeList[pos].value = nodeList[i].value;// 值不变
        
        startPos[col]++; // 该位置已使用，指向下一个位置
    }
    
    // 释放临时数组
    delete[] colCount;
    delete[] startPos;
}


void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    if (next == nullptr) {
        cout << "next array is null" << endl;
        return;
    }
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    if (nextVal == nullptr) {
        cout << "nextVal array is null" << endl;
        return;
    }
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
